package solution32;

import java.util.Stack;

/**
 * 32. Longest Valid Parentheses
 * https://leetcode.com/problems/longest-valid-parentheses/solution/
 * 求得是最长的合法（有效匹配括号）子串长度
 * Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.
 * For "(()", the longest valid parentheses substring is "()", which has length = 2.
 * Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.
 */
public class Solution {
    // O(n) O(n)
    // Instead of finding every possible string and checking its validity,
    // we can make use of stack while scanning the given string to check if the string scanned so far is valid,
    // and also the length of the longest valid string.
    // In order to do so, we start by pushing -1−1 onto the stack.
    public int longestValidParentheses(String s) {
        if (s == null || s.length() <= 1) return 0;
        int maxAns = 0;
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);
        int n = s.length();
        for (int i = 0; i < n; i++) {
            //For every text‘(’ encountered, we push its index onto the stack.
            if (s.charAt(i) == '(') {
                stack.push(i);
            } else {
                stack.pop();
                if (stack.empty()) {
                    stack.push(i);
                } else {
                    maxAns = Math.max(maxAns, i - stack.peek());
                }
            }
        }
        return maxAns;
    }

    // 动态规划 O(n) (On)
    // 关键是理解dp[i]表示的是什么！！！
    // We make use of a text dp array where ith element of text dp represents the length of the longest valid
    // substring ending at ith index.
    // s[i] = ')',and s[i-1] = '(' ---> dp[i]=dp[i-2]+2, 需要判断i-2是否溢出
    // s[i] = ')',and s[i-1] = ')' ,需要往前隔dp[i-1]个，判断位置i-dp[i-1]-1是否是'(' ，同样需要判断i-dp[i-1]-1是否大于0
    // 若是'(' ---> dp[i] = dp[i - 1] + dp[i - dp[i - 1] - 2] + 2; 同样需要判断(i - dp[i - 1]-2)是否大于0
    // 例如:()()(()),在判断最后一个(位置i=7）'）'时，由于倒数第2个(位置i-1=6)也是'）'，而以位置6位')'为结尾的dp[i-1]=2
    // 往前dp[i-1]+1个，位置i-dp[i-1]-1处为'（',那么，dp[i]=dp[i-1]+2；
    // 而再往前1个，即以位置i-dp[i-1]-2为结尾的dp[i-dp[i-1]-2]=2,说明之前的2个也合法，因此，要再加上dp[i-dp[i-1]-2]才是最长的。
    public int longestValidParentheses2(String s) {
        int maxAns = 0;
        int dp[] = new int[s.length()];
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == ')') {
                if (s.charAt(i - 1) == '(') {
                    dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
                } else if (i - dp[i - 1] > 0 && s.charAt(i - dp[i - 1] - 1) == '(') {
                    dp[i] = dp[i - 1] + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
                }
                maxAns = Math.max(maxAns, dp[i]);
            }
        }
        return maxAns;
    }
    // O(n) O(1)
    public int longestValidParentheses3(String s) {
        int left = 0, right = 0, maxLength = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                left++;
            } else {
                right++;
            }
            if (left == right) {
                maxLength = Math.max(maxLength, 2 * right);
            } else if (right >= left) {
                left = right = 0;
            }
        }
        left = right = 0;
        for (int i = s.length() - 1; i >= 0; i--) {
            if (s.charAt(i) == '(') {
                left++;
            } else {
                right++;
            }
            if (left == right) {
                maxLength = Math.max(maxLength, 2 * left);
            } else if (left >= right) {
                left = right = 0;
            }
        }
        return maxLength;
    }
}
